package com.javabasic.algorithm.leetcode;

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [2697. 字典序最小回文串 - 力扣（LeetCode）](https://leetcode.cn/problems/lexicographically-smallest-palindrome/description/?envType=daily-question&envId=2023-12-13)
 * @since Created by work on 2023/12/13 20:54
 */
public class LexicographicallySmallestPalindrome {

    @ParameterizedTest
    @MethodSource("inputData")
    public void testMakeSmallestPalindrome(String s) {
        System.out.println(makeSmallestPalindrome(s));
    }

    public static Stream<String> inputData() {
        return Stream.of("egcfe", "abcd", "seven");
    }


    public String makeSmallestPalindrome(String s) {

        if (s == null || s.isBlank()) {
            return s;
        }

        int len = s.length();
        int right = 0;
        int left = len - 1;
        char[] result = new char[len];
        while (right < left) {
            if (s.charAt(right) == s.charAt(left)) {
                result[right] = result[left] = s.charAt(right);

            } else if (s.charAt(right) < s.charAt(left)) {
                result[right] = result[left] = s.charAt(right);

            } else {
                result[right] = result[left] = s.charAt(left);
            }
            right++;
            left--;
        }

        if (right == left) {
            result[right] = s.charAt(right);
        }
        return String.valueOf(result);
    }

    /**
     * 更加高效的实现方法
     * @param s
     * @return
     */
    public String makeSmallestPalindrome2(String s) {

        if (s == null || s.isBlank()) {
            return s;
        }

        int len = s.length();
        int right = 0;
        int left = len - 1;
        char[] result = s.toCharArray();
        while (right < left) {
            if (result[right] < result[left]) {
                result[left] = result[right];

            } else {
                result[right] = result[left];
            }
            right++;
            left--;
        }

        return String.valueOf(result);
    }
}
